package com.waiting.leetcode;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/13
 **/
public class StoneGame877 {
    public static void main(String[] args) {

    }

    private int[] p;        //copy of piles
    private int[][] dp;     //solved subproblems

//    public boolean stoneGame(int[] piles) {
//        p = piles;
//        int len = piles.length;
//        dp = new int[len][len];
//        return dp(0, len - 1) > 0;
//    }
//
//    private int dp(int lo, int hi) {
//        if (lo == hi) {
//            return 0;
//        }
//        if (dp[lo][hi] != 0) {
//            return dp[lo][hi];
//        }
//        int res = 0;
//        if ((hi - lo + 1) % 2 == 0) {
//            res = Math.max(dp(lo + 1, hi) + p[lo], dp(lo, hi - 1) + p[hi]);
//        } else {
//            res = Math.min(dp(lo + 1, hi) - p[lo], dp(lo, hi - 1) - p[hi]);
//        }
//        dp[lo][hi] = res;
//        return res;
//    }
    public boolean stoneGame(int[] piles) {
        Helper[][] dp = new Helper[piles.length][piles.length];
        for (int i = 0; i < piles.length - 1; ++i) {
            dp[i][i+1] = new Helper();
            dp[i][i+1].first = Math.max(piles[i], piles[i+1]);
            dp[i][i+1].second = Math.min(piles[i], piles[i+1]);
        }
        for (int len = 3; len <= piles.length; ++len) {
            for (int i = 0; i + len <= piles.length; ++i) {
                int j = i + len - 1;
                dp[i][j] = new Helper();
                // case 1:
                dp[i][j].first = dp[i][j-1].second + piles[j];
                dp[i][j].second = dp[i][j-1].first;

                if (dp[i+1][j].second + piles[i] > dp[i][j].first) {
                    dp[i][j].first = dp[i+1][j].second + piles[i];
                    dp[i][j].second = dp[i+1][j].first;
                }
            }
        }
        return dp[0][piles.length-1].first > dp[0][piles.length-1].second;
    }
}
class Helper {
    public int first;
    public int second;
    public Helper() {
        first = 0;
        second = 0;
    }
}